1. A finite set of vertices also called nodes.
2. A finite set of ordered pair of the form (u, v) called as edge. The pair is ordered because (u, v) is not the same as (v, u) in case of a directed graph(digraph). The pair of the form (u, v) indicates that there is an edge from vertex u to vertex v. The edges may contain weight/value/cost.

• Graphs are used to represent networks. The networks may include paths in a city or telephone network or circuit network. For example Google GPS
• Graphs are also used in social networks like linkedIn, Facebook. For example, in Facebook, each person is represented with a vertex(or node). Each node is a structure and contains information like person id, name, gender and locale.

Directed and Undirected Graphs

• Directed Graphs: The Directed graphs are such graphs in which edges are directed in a single direction.
  
  For Example, the below graph is a directed graph:
  
  
• Undirected Graphs: Undirected graphs are such graphs in which the edges are directionless or in other words bi-directional. That is, if there is an edge between vertices u and v then it means we can use the edge to go from both u to v and v to u.
  
  Following is an example of an undirected graph with 5 vertices:
  
  

Representing Graphs

1. Adjacency Matrix.
2. Adjacency List.

• Adjacency Matrix: The Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j. Adjacency matrix for undirected graph is always symmetric. Adjacency Matrix is also used to represent weighted graphs. If adj[i][j] = w, then there is an edge from vertex i to vertex j with weight w.
  
  The adjacency matrix for the above example undirected graph is:
  
  
  Pros: Representation is easier to implement and follow. Removing an edge takes O(1) time. Queries like whether there is an edge from vertex 'u' to vertex 'v' are efficient and can be done O(1).
  
  Cons: Consumes more space O(V^2). Even if the graph is sparse(contains less number of edges), it consumes the same space. Adding a vertex is O(V^2) time.
  Please see this for a sample Python implementation of adjacency matrix.
  


• Adjacency List: Graph can also be implemented using an array of lists. That is every index of the array will contain a complete list. Size of the array is equal to the number of vertices and every index i in the array will store the list of vertices connected to the vertex numbered i. Let the array be array[]. An entry array[i] represents the list of vertices adjacent to the ith vertex. This representation can also be used to represent a weighted graph. The weights of edges can be represented as lists of pairs. Following is the adjacency list representation of the above example undirected graph.
  
  
  
  Below is the implementation of the adjacency list representation of Graphs:
  
  Note: In below implementation, we use dynamic arrays (vector in C++/ArrayList in Java) to represent adjacency lists instead of a linked list. The vector implementation has advantages of cache friendliness.
  
  
  C++

  XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

  Run

  Java

  XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

  Run

  Output:
  

   Adjacency list of vertex 0
   head -> 1-> 4
  
   Adjacency list of vertex 1
   head -> 0-> 2-> 3-> 4
  
   Adjacency list of vertex 2
   head -> 1-> 3
  
   Adjacency list of vertex 3
   head -> 1-> 2-> 4
  
   Adjacency list of vertex 4
   head -> 0-> 1-> 3
  

  
  Pros: Saves space O(|V|+|E|). In the worst case, there can be C(V, 2) number of edges in a graph thus consuming O(V^2) space. Adding a vertex is easier.
  
  Cons: Queries like whether there is an edge from vertex u to vertex v are not efficient and can be done O(V).

1. Create a boolean array say visited[] of size V+1 where V is the number of vertices in the graph.
2. Create a Queue, mark the source vertex visited as visited[s] = true and push it into the queue.
3. Until the Queue is non-empty, repeat the below steps:
   
   • Pop an element from the queue and print the popped element.
   • Traverse all of the vertices adjacent to the vertex poped from the queue.
   • If any of the adjacent vertex is not already visited, mark it visited and push it to the queue.

Consider the graph shown in the below Image. The vertices marked blue are not-visited vertices and the vertices marked yellow are visited. The vertex numbered 1 is the source vertex, i.e. the BFS traversal will start from the vertex 1.

Following the BFS algorithm:

• Mark the vertex 1 visited in the visited[] array and push it to the queue.

Step 3: POP the vertex at the front of queue that is 1, and print it.

Step 4: Check if adjacent vertices of the vertex 1 are not already visited. If not, mark them visited and push them back to the queue.

 
 

Step 5:

• POP the vertex at front that is 2 and print it.
• Check if the adjacent vertices of 2 are not already visited. If not, mark them visited and push them to queue. So, push 4 and 5.

Step 6:

• POP the vertex at front that is 3 and print it.
• Check if the adjacent vertices of 3 are not already visited. If not, mark them visited and push them to queue. So, donot push anything.

 

Step 7:

• POP the vertex at front that is 4 and print it.

Step 8:

• Check if the adjacent vertices of 4 are not already visited. If not, mark them visited and push them to queue. So, push 6 to the queue.

Step 9:

• POP the vertex at front, that is 5 and print it.
• Since, all of its adjacent vertices are already visited, donot push anything.

Step 10:

• POP the vertex at front, that is 6 and print it.
• Since, all of its adjacent vertices are already visited, donot push anything.
  

 
 

Since the Queue is empty now, it means that the complete graph is traversed.

1 2 3 4 5 6

Step 1: Consider the below graph and apply the DFS algorithm recursively for every node using an auxiliary stack for recursive calls and an array to keep track of visited vertices.

Step 2: Process the vertex A, mark it visited and call DFS for its adjacent vertices. Suppose the first adjacent vertex processed is B. The vertex A is put on the auxilary stack for now.

 

Step 3: Process the vertex B, mark it visited and call DFS for its adjacent vertices. Suppose the first adjacent vertex processed is D. The vertex B is put on the auxilary stack for now.

Step 4: Process the vertex D, mark it visited and call DFS for its adjacent vertices. Suppose the first adjacent vertex processed is E. The vertex D is put on the auxilary stack for now.

Step 5: Process the vertex E, mark it visited and call DFS for its adjacent vertices. Suppose the first adjacent vertex processed is F. The vertex E is put on the auxilary stack
for now.

Step 6: Process the vertex F, mark it visited and call DFS for its adjacent vertices. There are no adjacent vertex of the vertex F, so backtrack to find a new path. The vertex F is put on the auxilary stack for now.

Step 7: Since the vertex F has no adjacent vertices left unvisited, backtrack and go to previous call, that is process any other adjacent vertex of node E, that is C.

Step 8: Process the vertex C, mark it visited and call DFS for its adjacent vertices. The vertex C is put on the auxilary stack for now.

 

Step 9: Since there are no adjacent vertex of C, backtrack to find a new path and keep removing nodes from stack until a new path is found. Since all of the nodes are processed so the stack will get empty.

Following is Depth First Traversal (starting from vertex 2)
2 0 1 3

Graph contains cycle

Given a graph and a source vertex in the graph, find the shortest paths from source to all vertices in the given graph.

1. Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty.
2. Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign distance value as 0 for the source vertex so that it is picked first.
3. While sptSet doesn't include all vertices:
   
   • Pick a vertex u which is not there in sptSet and has minimum distance value.
   • Include u to sptSet.
   • Update distance value of all adjacent vertices of u. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex v, if sum of distance value of u (from source) and weight of edge u-v, is less than the distance value of v, then update the distance value of v.

1) Initialize distances of all vertices as infinite.

2) Create an empty priority_queue pq. Every item
   of pq is a pair (weight, vertex). Weight (or 
   distance) is used as the first item of pair
   as the first item is by default used to compare
   two pairs

3) Insert source vertex into pq and make its
   distance as 0.

4) While either pq doesn't become empty
    a) Extract minimum distance vertex from pq. 
       Let the extracted vertex be u.
    b) Loop through all adjacent of u and do 
       following for every vertex v.

           // If there is a shorter path to v
           // through u. 
           If dist[v] > dist[u] + weight(u, v)

               (i) Update distance of v, i.e., do
                     dist[v] = dist[u] + weight(u, v)
               (ii) Insert v into the pq (Even if v is
                    already there)
               
5) Print distance array dist[] to print all shortest
   paths. 

Vertex   Distance from Source

0                0

1                4

2                12

3                19

4                21

5                11

6                9

7                8

8                14

• Input: Graph and a source vertex src.
• Output: Shortest distance to all vertices from src. If there is a negative weight cycle, then shortest distances are not calculated, negative weight cycle is reported.

1. This step initializes distances from source to all vertices as infinite and distance to source itself as 0. Create an array dist[] of size |V| with all values as infinite except dist[src] where src is source vertex.
   
2. This step calculates shortest distances. Do following |V|-1 times where |V| is the number of vertices in given graph.
   Do following for each edge u-v:
   
   • If dist[v] > dist[u] + weight of edge uv, then update dist[v] as: dist[v] = dist[u] + weight of edge uv.
3. This step reports if there is a negative weight cycle in graph. Do following for each edge u-v. If dist[v] > dist[u] + weight of edge uv, then "Graph contains negative weight cycle".
   

Vertex   Distance from Source
0                0
1                -1
2                2
3                -2
4                1

1. Negative weights are found in various applications of graphs. For example, instead of paying the cost for a path, we may get some advantage if we follow the path.
2. Bellman-Ford works better (better than Dijkstra's) for distributed systems. Unlike Dijksra's where we need to find the minimum value of all vertices, in Bellman-Ford, edges are considered one by one.

1) Initialize all vertices as not visited.
2) Do following for every vertex 'v'.
       (a) If 'v' is not visited before, call DFSUtil(v)
       (b) Print new line character

// This Function performs DFS traversal
// of vertex v.
DFSUtil(v)
1) Mark 'v' as visited.
2) Print 'v'
3) Do following for every adjacent 'u' of 'v'.
     If 'u' is not visited, then recursively call DFSUtil(u)

Following are connected components 
0 1 2 
3 4

What is Minimum Spanning Tree?

Prim's Algorithm

1. Create a set mstSet that keeps track of vertices already included in MST.
2. Assign a key value to all vertices in the input graph. Initialize all key values as INFINITE. Assign key value as 0 for the first vertex so that it is picked first.


3. While mstSet doesn't include all vertices:
   
   • Pick a vertex u which is not there in mstSet and has minimum key value.
   • Include u to mstSet.
   • Update key value of all adjacent vertices of u. To update the key values, iterate through all adjacent vertices. For every adjacent vertex v, if weight of edge u-v is less than the previous key value of v, update the key value as weight of u-v.

How to implement the above algorithm?

Edge   Weight
0 - 1    2
1 - 2    3
0 - 3    6
1 - 4    5

How to find all articulation points in a given graph?

1. For every vertex v, do following:
   
   • Remove v from graph
   • See if the graph remains connected (We can either use BFS or DFS)
   • Add v back to the graph

1. u is the root of DFS tree and it has at least two children.


2. u is not the root of DFS tree and it has a child v such that no vertex in the subtree rooted with v has a back edge to one of the ancestors (in DFS tree) of u.

low[u] = min(disc[u], disc[w]) 
where w is an ancestor of u and there is a back edge from 
some descendant of u to w.

Articulation points in first graph
0 3
Articulation points in second graph
1 2
Articulation points in third graph
1

1. Create an empty stack 'S' and do DFS traversal of a graph. In DFS traversal, after calling recursive DFS for adjacent vertices of a vertex, push the vertex to stack. In the above graph, if we start DFS from vertex 0, we get vertices in the stack as 1, 2, 4, 3, 0.
2. Reverse directions of all arcs to obtain the transpose graph.
3. One by one pop a vertex from S while S is not empty. Let the popped vertex be 'v'. Take v as source and do DFS (call DFSUtil(v)). The DFS starting from v prints strongly connected component of v. In the above example, we process vertices in order 0, 3, 4, 2, 1 (One by one popped from stack).

How does this work?

Following are strongly connected components in given graph

0 1 2

3

4

How to find all bridges in a given graph?

1. For every edge (u, v), do following
   
   • Remove (u, v) from graph.
   • See if the graph remains connected (We can either use BFS or DFS)
   • Add (u, v) back to the graph.

Bridges in first graph

3 4

0 3



Bridges in second graph

2 3

1 2

0 1



Bridges in third graph

1 6

Problem #1 : Find the number of islands

Input : mat[][] = {{1, 1, 0, 0, 0},
                   {0, 1, 0, 0, 1},
                   {1, 0, 0, 1, 1},
                   {0, 0, 0, 0, 0},
                   {1, 0, 1, 0, 1} 
Output : 5

                        {1,  1, 0, 0, 0},
                        {0, 1, 0, 0, 1},
                        {1, 0, 0, 1, 1},
                        {0, 0, 0, 0, 0},
                        {1, 0, 1, 0, 1}

// A utility function to do DFS for a 
// 2D boolean matrix. It only considers 
// the 8 neighbours as adjacent vertices 
void DFS(int M[][COL], int row, int col, 
         bool visited[][COL]) 
{ 
    // These arrays are used to get 
    // row and column numbers of 8 
    // neighbours of a given cell 
    rowNbr[] = { -1, -1, -1, 0, 0, 1, 1, 1 }
    colNbr[] = { -1, 0, 1, -1, 1, -1, 0, 1 }
  
    // Mark this cell as visited 
    visited[row][col] = true
  
    // Recur for all connected neighbours 
    for (int k = 0; k < 8; ++k) 
        if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited)) 
            DFS(M, row + rowNbr[k], col + colNbr[k], visited)
} 
  
// The main function that returns 
// count of islands in a given boolean 
// 2D matrix 
int countIslands(int M[][COL]) 
{ 
    // Make a bool array to mark visited cells. 
    // Initially all cells are unvisited 
    bool visited[ROW][COL]
    memset(visited, 0, sizeof(visited))
  
    // Initialize count as 0 and 
    // travese through the all cells of 
    // given matrix 
    int count = 0
    for (int i = 0; i < ROW; ++i) 
        for (int j = 0; j < COL; ++j) 
  
            // If a cell with value 1 is not 
            if (M[i][j] && !visited[i][j]) { 
                // visited yet, then new island found 
                // Visit all cells in this island. 
                DFS(M, i, j, visited) 
  
                // and increment island count 
                ++count
            } 
  
    return count
}

Problem #2 : Detect Cycle in a Directed Graph

// Utility function to check back edge in a directed graph
bool isCyclicUtil(int v, bool visited[], bool *recStack) 
{ 
    if(visited[v] == false) 
    { 
        // Mark the current node as visited and part of recursion stack 
        visited[v] = true
        recStack[v] = true
  
        // Recur for all the vertices adjacent to this vertex 
        list < int > :: iterator i
        for(i = adj[v].begin(); i != adj[v].end(); ++i) 
        { 
            if ( !visited[*i] && isCyclicUtil(*i, visited, recStack) ) 
                return true
            else if (recStack[*i]) 
                return true
        } 
  
    } 
    recStack[v] = false;  // remove the vertex from recursion stack 
    return false; 
} 
  
// Returns true if the graph contains a cycle, else false.  
bool isCyclic() 
{ 
    // Mark all the vertices as not visited and not part of recursion 
    // stack 
    bool *visited = new bool[V]
    bool *recStack = new bool[V]
    for(int i = 0; i < V; i++) 
    {
        visited[i] = false
        recStack[i] = false
    } 
  
    // Call the recursive helper function to detect cycle in different 
    // DFS trees 
    for(int i = 0; i < V; i++) 
        if (isCyclicUtil(i, visited, recStack)) 
            return true
  
    return false
} 

Problem #3 : Topological Sorting

// A recursive function used by topological sort 
void topologicalSortUtil(int v, bool visited[],  
                                stack &Stack) 
{ 
    // Mark the current node as visited. 
    visited[v] = true
  
    // Recur for all the vertices adjacent to this vertex 
    list < int > :: iterator i
    for (i = adj[v].begin(); i != adj[v].end(); ++i) 
        if (!visited[*i]) 
            topologicalSortUtil(*i, visited, Stack); 
  
    // Push current vertex to stack which stores result 
    Stack.push(v)
} 
  
// The function to do Topological Sort. It uses recursive  
// topologicalSortUtil() 
void topologicalSort() 
{ 
    stack < int > Stack
  
    // Mark all the vertices as not visited 
    bool *visited = new bool[V]
    for (int i = 0; i < V; i++) 
        visited[i] = false
  
    // Call the recursive helper function to store Topological 
    // Sort starting from all vertices one by one 
    for (int i = 0; i < V; i++) 
      if (visited[i] == false) 
        topologicalSortUtil(i, visited, Stack)
  
    // Print contents of stack 
    // Topological Order
    while (Stack.empty() == false) 
    { 
        print(Stack.top()) 
        Stack.pop()
    } 
}

Problem #4 : Minimum time required to rot all oranges

0: Empty cell
1: Cells have fresh oranges
2: Cells have rotten oranges

Input:  arr[][C] = { {2, 1, 0, 2, 1},
                     {1, 0, 1, 2, 1},
                     {1, 0, 0, 2, 1}};
Output:
All oranges can become rotten in 2 time frames.


Input:  arr[][C] = { {2, 1, 0, 2, 1},
                     {0, 0, 1, 2, 1},
                     {1, 0, 0, 2, 1}};
Output:
All oranges cannot be rotten.

1) Create an empty Q.
2) Find all rotten oranges and enqueue them to Q. Also enqueue a delimiter to indicate the beginning of next time frame.
3) While Q is not empty do following
....3.a) Do following while delimiter in Q is not reached
........ (i) Dequeue an orange from queue, rot all adjacent oranges. While rotting the adjacent, make sure that the time frame is incremented only once. And the time frame is not incremented if there are no adjacent oranges.
....3.b) Dequeue the old delimiter and enqueue a new delimiter. The oranges rotten in the previous time frame lie between the two delimiters.

// This function finds if it is possible to rot all oranges or not.
// If possible, then it returns minimum time required to rot all,
// otherwise returns -1
int rotOranges(int arr[][C])
{
    // Create a queue of cells
    queue < cell > Q
    cell temp
    ans = 0
    // Store all the cells having rotten orange in first time frame
    for (int i=0; i < R; i++)
    {
       for (int j=0; j < C; j++)
       {
            if (arr[i][j] == 2)
            {
                temp.x = i
                temp.y = j
                Q.push(temp)
            }
        }
    }
    // Separate these rotten oranges from the oranges which will rotten
    // due the oranges in first time frame using delimiter which is (-1, -1)
    temp.x = -1
    temp.y = -1
    Q.push(temp)
    // Process the grid while there are rotten oranges in the Queue
    while (!Q.empty())
    {
        // This flag is used to determine whether even a single fresh
        // orange gets rotten due to rotten oranges in current time
        // frame so we can increase the count of the required time.
        bool flag = false
        // Process all the rotten oranges in current time frame.
        while (!isdelim(Q.front()))
        {
            temp = Q.front()
            // Check right adjacent cell that if it can be rotten
            if (isvalid(temp.x+1, temp.y) && arr[temp.x+1][temp.y] == 1)
            {
                // if this is the first orange to get rotten, increase
                // count and set the flag.
                if (!flag) ans++, flag = true

                // Make the orange rotten
                arr[temp.x+1][temp.y] = 2

                // push the adjacent orange to Queue
                temp.x++
                Q.push(temp)

                temp.x-- // Move back to current cell
            }
            // Check left adjacent cell that if it can be rotten
            if (isvalid(temp.x-1, temp.y) && arr[temp.x-1][temp.y] == 1) {
                if (!flag) ans++, flag = true
                arr[temp.x-1][temp.y] = 2
                temp.x--
                Q.push(temp) // push this cell to Queue
                temp.x++
            }
            // Check top adjacent cell that if it can be rotten
            if (isvalid(temp.x, temp.y+1) && arr[temp.x][temp.y+1] == 1) {
                if (!flag) ans++, flag = true
                arr[temp.x][temp.y+1] = 2
                temp.y++
                Q.push(temp) // Push this cell to Queue
                temp.y--
            }
            // Check bottom adjacent cell if it can be rotten
            if (isvalid(temp.x, temp.y-1) && arr[temp.x][temp.y-1] == 1) {
                if (!flag) ans++, flag = true
                arr[temp.x][temp.y-1] = 2
                temp.y--
                Q.push(temp) // push this cell to Queue
            }
            Q.pop()
        }
        // Pop the delimiter
        Q.pop()
        // If oranges were rotten in current frame than separate the
        // rotten oranges using delimiter for the next frame for processing.
        if (!Q.empty()) {
            temp.x = -1
            temp.y = -1
            Q.push(temp)
        }
        // If Queue was empty than no rotten oranges left to process so exit
    }
    // Return -1 if all arranges could not rot, otherwise -1.
    return (checkall(arr))? -1: ans
}